/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        122.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/9 15:04
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//给定一个数组，它的第i 个元素是一支给定股票第 i 天的价格。
//
//设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
//
//注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
#include "../header.h"
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        /*
        k == infinity 买入次数
        dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k-1][0] - prices[i])
                = max(dp[i - 1][k][1], dp[i-1][k][0] - prices[i])
        dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k][1] + prices[i])

         ==> k都存在，可以消去
        dp[i][1] = max(dp[i - 1][1], dp[i-1][0] - prices[i])
        dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i])
         */
        int n = prices.size();
        int dp_i_0 = 0, dp_i_1 = INT_MIN;
        for (int i = 0; i < n; ++i) {
            int temp = dp_i_0;
            dp_i_0 = max(dp_i_0,dp_i_1 + prices[i]);
            dp_i_1 = max(dp_i_1,temp - prices[i]);
        }
        return dp_i_0;
    }
};
